package demo21;

public class sort {

    //利用快速排序中霍尔法:以头值或尾值为基准，右标记移动找到比基准值小的，左标记后移找到比基准值大的，两者交换，重复执行直到左右标记重合
    //将重合处与基准值交换，返回其位置，之后分别以此方法排序左边与右边
    public void quickSort(int[]array){
        if(array==null||array.length<=1){
            return;
        }
        quick(array,0,array.length-1);
    }
    private void quick(int[]array,int start,int end){
        if(start>=end){
            return;
        }
        int privor=partion(array,start,end);//返回值left与right重合
        quick(array,start,privor-1);//排序重合处的左边
        quick(array,privor+1,end);//排序重合处的右边
    }
    public int partion(int[]array,int left,int right){
        int temp=left;
        int templeft=array[left];
        while(left<right) {
            while (left < right && array[right] >= templeft) {
                right--;
            }
            while (left < right && array[left] <= templeft) {
                left++;
            }
            swap(array, right, left);
        }
        swap(array,left,temp);
        return left;
    }
    private void swap(int[]array,int right,int left){
        int temp=array[right];
        array[right]=array[left];
        array[left]=temp;
    }
    //快速排序，挖坑法思路：以头值作为基准值且保存，右标记移动找到比头值小的，把它放在头值处，左标记移动找到比保存头值大的，放入右标记留下的坑，直到
    //左右标记重合，把保存头值放入重合的坑处，并返回，之后排左边与右边即可
    public void quickSort2(int[]array){
        quick2(array,0,array.length-1);
    }
    public void quick2(int []array,int left,int right){
        if(array.length==0){
            return;
        }
        int privor=partion2(array,left,right);
        quick(array,left,privor-1);
        quick(array,privor+1,right);
    }

    public int partion2(int[] array,int left,int right){
        int temp=left;
        int templeft=array[left];
        while (left<right){
            while (left<right&&array[right]>=templeft){
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left]<=templeft){
                left++;
            }
            array[right]=array[left];
            array[left]=templeft;
        }
        return left;
    }
    //前后指针法:以头值为基准值，头标记与头标记的下一个cur，cur向后走若找到比基准值小的，且头标记向前走一步得到的元素不等于cur的元素值，交换
    //头标记与cur标记对应的值，直到cur大于最右边标记，把头标记对应的值与基准值交换，返回头标记，再排左边和右边即可
    public void quickSort3(int[]array){
        quick3(array,0,array.length-1);
    }
    public void quick3(int []array,int start,int end){
        if(array.length==0||start>=end){
            return;
        }

        int privor=partion3(array,start,end);
        quick3(array,start,privor-1);
        quick3(array,privor+1,end);
    }
    public int partion3(int []array,int left,int right){
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if(array[cur]<array[left]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }
}
